package main

import "sort"

func countPairs(n int, edges [][]int) int64 {
	dots := make([]int, n)
	m := make(map[int]int, 0)
	for i := 0; i < n; i++ {
		dots[i] = i
	}
	for i := 0; i < len(edges); i++ {
		if edges[i][1] < edges[i][0] {
			edges[i][1], edges[i][0] = edges[i][0], edges[i][1]
		}
	}
	sort.Slice(edges, func(i, j int) bool {
		return edges[i][0] < edges[j][0]
	})
	for i := 0; i < len(edges); i++ {
		dots[edges[i][1]] = dots[edges[i][0]]
		// 不知道给的图是不是有序边
		// 现在知道了。。不是
	}
	for _, val := range dots {
		m[val]++
	}
	var sum int64 = 0
	k := 0
	//s := make([]int, len(m))
	for _, val := range m {
		sum += int64(val * k)
		k += val
	}
	//for i := 0; i < len(m); i++ {
	//	for j := i + 1; j < len(m); j++ {
	//		sum += int64(s[i] * s[j])
	//	}
	//}
	return sum
}

/*
func countPairs(n int, edges [][]int) (ans int64) {

	g := make([][]int, n)

	for _, e := range edges {

		a, b := e[0], e[1]

		g[a] = append(g[a], b)

		g[b] = append(g[b], a)

	}

	vis := make([]bool, n)

	var dfs func(int) int

	dfs = func(i int) int {

		if vis[i] {

			return 0

		}

		vis[i] = true

		cnt := 1

		for _, j := range g[i] {

			cnt += dfs(j)

		}

		return cnt

	}

	var s int64

	for i := 0; i < n; i++ {

		t := int64(dfs(i))

		ans += s * t

		s += t

	}

	return

}

*/

func main() {
	countPairs(7, [][]int{{0, 2}, {0, 5}, {2, 4}, {1, 6}, {5, 4}})
}
